package java学习.代码随想录.动态规划.背包;

import java.util.Arrays;

/**
 * **************
 * 项目名称: 蓝桥杯-Java学习 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦Lenovo <br/>
 * 创建时间: 2022/8/24 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 完全平方数 {
    public static int numSquares(int n) {
/**
    返回 和为 n 的完全平方数的最少数量
 *  背包容量： n
 *  1. dp[j] 背包容量为j 的完全平方数的最小数量
 *  2.  dp[j]  = Math.min(dp[j],dp[j-con[i]]+1);
 *  3. 遍历顺序： 求的是最小数量：组合数。
 *  4. 初始化： dp[0] = 0.
 */
    int max = Integer.MAX_VALUE;
    int []dp = new int[n+1];
    int[] con = new int[n+1];
    for (int i = 0; i < con.length; i++) {
        con[i] = i*i;
        dp[i] = max;
    }
        dp[0] = 0;
    for (int i = 0; i <con.length;i++ ) {

        for (int j = con[i]; j <=n; j++) {
            if (dp[j-con[i]]!=max){
            dp[j]  = Math.min(dp[j],dp[j-con[i]]+1);
            }
        }
    }
        System.out.println(Arrays.toString(con));

        System.out.println(Arrays.toString(dp));
        return dp[n]==max?-1:dp[n];
    }

    public static void main(String[] args) {
        System.out.println(numSquares(13));
    }
}
